#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
//https://www.luogu.com.cn/problem/P2043
using namespace std;
int n;

const int N = 1e4 + 10;
int c[N];

void deprime(int n)
{
	while (n > 1)
	{
		int x = n--;
		for (int i = 2; i <= x / i; ++i)
		{
			int cnt = 0;
			while (x % i == 0)
			{
				x /= i;
				cnt++;
			}
			c[i] += cnt;
		}
		c[x]++;
	}

}



int main()
{
	cin >> n;

	deprime(n);

	for (int i = 2; i <= n; ++i)
	{
		if (c[i])
			cout << i << ' ' << c[i] << endl;
	}


	return 0;
}